1455. Цикл

Дан граф. Определить, есть ли в нем цикл отрицательного веса, и если да, то вывести его.

Вход. Первая строка содержит количество вершин графа n (1 ≤ n ≤ 100). В следующих n строках находится по n чисел - матрица смежности графа. Веса ребер не превышают по модулю 10000. Если ребра нет, соответствующее значение равно 100000.

Выход. В первой строке выведите "YES", если цикл существует, или "NO" в противном случае. При наличии цикла выведите во второй строке количество вершин в нем (считая одинаковыми первую и последнюю) и в третьей строке - вершины, входящие в этот цикл в порядке обхода. Если циклов несколько - выведите любой.

Пример входа	Пример выхода
2 0 -1 -1 0	YES 3 1 2 1

РЕШЕНИЕ

графы – алгоритм Беллмана - Форда

Анализ алгоритма

Запустим на графе алгоритм Флойда-Уоршела. Если для некоторого i значение g[i][i] < 0, то существует путь отрицательной длины из i в i. При этом сам простой цикл не обязательно проходит через i.

Пусть граф содержит 100 вершин, часть которого изображена на рисунке. Через 100 итераций станет g[1][1] < 0, хотя цикл отрицательной длины не проходит через 1.

Запустим алгоритм Беллмана – Форда начиная с такого значения start, для которого g[start][start] < 0. Будем также пересчитывать массив предков p, чтобы по нему можно было восстановить путь. Совершим |V| = n шагов назад по массиву предков, начиная с вершины start. Мы попадем в вершину y, которая однозначно находится на цикле отрицательной длины. Остается от вершины y по массиву предков пройти назад, получив искомый цикл в реверсивном виде. Переворачиваем и выводим цикл.

Реализация алгоритма

Взвешенный граф с не более чем MAX вершинами храним в матрице расстояний m.

#define MAX 110

#define INF 0x3F3F3F3F

int m[MAX][MAX];

int d[MAX], p[MAX];

int cycle [2*MAX], ptr;

Алгоритм Флойда – Уоршела.

int Floyd_Warshal(void)

{

int i, j, k;

int g[MAX][MAX];

memcpy(g,m,sizeof(m));

for(k = 1; k <= n; k ++)

for(i = 1; i <= n; i++)

for(j = 1; j <= n; j++)

g[i][j] = min(g[i][j], g[i][k] + g[k][j]);

Если по окончанию алгоритма для некоторого i значение g[i][i] < 0, то существует путь отрицательной длины из i в i (то есть цикл).

for(i = 1; i <= n; i++)

if(g[i][i] < 0) return i;

return 0;

}

Запустим алгоритм Беллмана - Форда из вершины Source.

void Bellman_Ford(int Source)

{

int stage, i, j;

memset(d,0x3F,sizeof(d));

memset(p,-1,sizeof(p));

d[Source] = 0;

for(stage = 0; stage < n; stage++)

Перебираем все ребра графа – проходим по матрице расстояний.

for (i = 1; i <= n; i++)

for (j = 1; j <= n; j++)

{

if ((d[i] < INF) && (m[i][j] != INF))

if (d[j] > d[i] + m[i][j])

{

d[j] = d[i] + m[i][j];

p[j] = i;

}

}

Вершина Source не обязательно лежит на искомом цикле. Совершим от нее n шагов назад по массиву предков. При этом мы попадем в вершину y, лежащую на цикле отрицательной длины.

int y = Source;

for(i = 1; i <= n; i++)

y = p[y];

Вершина y находится на цикле отрицательной длины. Двигаемся от нее назад по массиву предков пока не дойдем до y снова, получив искомый цикл в реверсивном виде.

ptr = 0;

cycle[ptr++] = y;

int cur = p[y];

while(cur != y)

{

cycle[ptr++] = cur;

cur = p[cur];

}

cycle[ptr++] = y;

Переворачиваем найденный цикл.

for(i = 0; i < ptr - i - 1; i++)

{

int temp = cycle[i];

cycle[i] = cycle[ptr - i - 1];

cycle[ptr - i - 1] = temp;

}

}

Основная часть программы. Читаем входной граф в весовую матрицу m.

scanf("%d",&n);

for(i = 1; i <= n; i++)

for(j = 1; j <= n; j++)

{

scanf("%d",&m[i][j]);

if (m[i][j] == 100000) m[i][j] = INF;

}

start = Floyd_Warshal();

Если цикла отрицательного веса не существует, то завершаем работу.

if(start == 0) // no negative cycle

{

puts("NO");

return 0;

}

Bellman_Ford(start);

Выводим найденный цикл.

printf("YES\n%d\n",ptr);

for(i = 0; i < ptr - 1; i ++)

printf("%d ",cycle[i]);

printf("%d\n",cycle[ptr-1]);